1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,w=0;char c=getchar();
while(!isdigit(c))w|=c=='-',c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return w?-x:x;
}
const int maxn=1e5+10,maxm=2e5+10,INF=0x3f3f3f3f;
int n,m,s;
int ecnt,head[maxn],to[maxm],nxt[maxm],v[maxm];
inline void addedge(int a,int b,int c){
to[++ecnt]=b,nxt[ecnt]=head[a],head[a]=ecnt;v[ecnt]=c;
}
int dis[maxn];
bool vis[maxn];
inline void dijkstra(){
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
q.push(make_pair(0,s));
for(int i=1;i<=n;i++) dis[i]=INF;
dis[s]=0;
while(!q.empty()){
int x=q.top().second;q.pop();
if(vis[x])continue;
vis[x]=true;
for(int u,i=head[x];i;i=nxt[i]) if(dis[u=to[i]]>dis[x]+v[i])
dis[u]=dis[x]+v[i],q.push(make_pair(dis[u],u));
}
}
int main(){
n=read(),m=read(),s=read();
for(int a,b,i=1;i<=m;i++)a=read(),b=read(),addedge(a,b,read());
dijkstra();
for(int i=1;i<=n;i++)printf("%d ",dis[i]);
return 0;
}
|
